package org.magi.sort;

import org.magi.Utils;

/**
 * 2022.6.13 快速排序 1.0
 */
public class QuickSort implements Sort{
    @Override
    public int[] sort(int[] arr) {
        if (arr == null || arr.length < 2) { return arr; }
        doSort(arr, 0, arr.length - 1);
        return arr;
    }

    private void doSort(int[] arr, int form, int end) {
        if (end - form <= 1) {
            if (end - form == 1 && arr[form] > arr[end]) {
                Utils.switchPos(arr, form, end);
            }
            return;
        }
        int l = form, r = end;
        int base = arr[l];
        int k = form;
        while(l < r) {
            if (arr[r] < base) {
                Utils.switchPos(arr, l, r);
                k = r;
                while(l < r) {
                    l++;
                    if (arr[l] > base) {
                        Utils.switchPos(arr, l, r);
                        k = l;
                        break;
                    }
                }
            }
            r--;
        }
        if (k != form) {
            doSort(arr, form, k - 1);
        }
        if (k != end) {
            doSort(arr, k + 1, end);
        }
    }
}
